# -*- coding: utf-8 -*-
# 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
# 示例：
# 输入：1->2->4, 1->3->4
# 输出：1->1->2->3->4->4

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        head = ListNode(-1);
        current = head;
        while l1 and l2:
            if l1.val < l2.val:
                current.next = l1;
                l1 = l1.next;
            else:
                current.next = l2;
                l2 = l2.next;
            current = current.next;
        if l1:
            current.next = l1;
        if l2:
            current.next = l2;

        self.printList(head.next);
        return head.next;
    def printList(self, head):
        current = head;
        v_log = [];
        while current:
            v_log.append(current.val);
            current = current.next;
        print v_log;

t = Solution();
l1 = ListNode(1);
l1.next = ListNode(2);
l1.next.next = ListNode(4);

l2 = ListNode(1);
l2.next = ListNode(3);
l2.next.next = ListNode(4);
t.mergeTwoLists(l1, l2);